home *** CD-ROM | disk | FTP | other *** search
/ SPACE 2 / SPACE - Library 2 - Volume 1.iso / program / 561 / prolog / quiksort < prev    next >
Text File  |  1991-09-08  |  2KB  |  66 lines
  1.  
  2. % Demonstration für Prolog :
  3.  
  4. % QUICKSORT -- Sortieren von Listen, deren Elemente Integerzahlen sind
  5.  
  6. % Quelle : Prolog-Kursus 1985, TH Darmstadt
  7. %          (vermutlich mehr oder weniger direkt aus dem Clocksin/Mellish)
  8.  
  9. % Dieses Beispiel zeigt sehr deutlich, wie man in Prolog Probleme,
  10. % die in anderen Programmiersprachen (wie z.B. Pascal) ziemlich komplex
  11. % werden, auf einfache (einfachste ?) Weise lösen kann.
  12.  
  13. % Aufruf der Funktion :
  14.  
  15. %     qsort(Unsortierte_Liste, Sortierte_Liste)
  16.  
  17. %------------------------------------------------------------------------
  18.  
  19. % Definition des Prädikates 'qsort' :
  20.  
  21. qsort([], []).    % Die leere Liste ist schon sortiert.
  22.  
  23. qsort([K | R], E) :- % Das erste Element einer nichtleeren Liste wird benutzt,
  24.       split(R, K, E1, E2), % ... um die Liste in zwei Teillisten zu spalten,
  25.                            % von denen E1 die Elemente <= K und E2 die
  26.                            % Elemente > K enthält.
  27.  
  28.       qsort(E1, S1),       % Die beiden Teillisten werden getrennt sortiert.
  29.       qsort(E2, S2),
  30.  
  31.       append(S1, [K | S2], E).   % Die sortierten Teillisten (und das ehemalige
  32.                                  % erste Element) werden zusammengefügt.
  33.  
  34.  
  35. % Definition des Prädikates 'split' :
  36.  
  37. split([], _, [], []).      % Die leere Liste läßt sich nicht spalten.
  38.  
  39. split([X | R], K, [X | E1], E2) :- X =< K,   % Erstes Element <= K :
  40.                                              % einfügen in erste Teilliste.
  41.       split(R, K, E1, E2).                   % Rest der Liste aufspalten.
  42.  
  43. split([X | R], K, E1, [X | E2]) :- X > K,    % Erstes Element > K :
  44.                                              % einfügen in zweite Teilliste.
  45.       split(R, K, E1, E2).                   % Rest der Liste aufspalten.
  46.  
  47.  
  48. % Definition des Prädikates 'append' :
  49.  
  50. append([], L, L) :- !.
  51. append([K | R], L, [K | RL]) :- append(R, L, RL).
  52.  
  53. %-----------------------------------------------------------------------
  54.  
  55. % Mit dem folgenden Prädikat kann man die Geschwindigkeit des Sortierens
  56. % prüfen :
  57.  
  58. % Man ruft statt   ' qsort(..., ...) ' das Praädikat ' qtest(..., ...) ' auf.
  59. % 'qtest' gibt unmittelbar VOR und NACH dem Sortieren je ein Klingelzeichen
  60. % aus. Der Abstand der beiden Töne entspricht der benötigten Zeit.
  61.  
  62. qtest(X, Y) :- bell, qsort(X, Y), bell.
  63.  
  64. end.
  65.  
  66.